A file system may “leak” computer system resources—for example, a program or application may fail to release a resource that it will not use again, leading to exhaustion of that resource over time. The process of “garbage collection” is used by file systems to identify resources that are no longer in use and therefore can be freed up.
Some file systems utilize data structures such as inodes, each of which is identified by an index number (into an array). Inodes are allocated and freed when files are created and deleted by a user. An inode's allocation state is represented by setting a corresponding bit in a bitmap. Due to data corruption or inconsistencies resulting from operator error, hardware failure, firmware problems, etc., some inodes may no longer be used (referenced) by the file system but may still be marked as in use in the bitmap. If these unused (unreferenced) inodes are not identified, then it is possible that all inode numbers will eventually be assigned and numbers for new inodes will not be available.
Similarly, some data blocks may no longer be referred to by an inode but, for reasons such as those mentioned above, may not have been deleted from memory. If unreferenced data blocks are not identified, then they may begin to accumulate and consume a large number of data blocks.
A utility such as a file system consistency check (FSCK) can be used for garbage collection to identify unreferenced inodes and data blocks that are erroneously marked as referenced (allocated). However, the conventional FSCK garbage collection process maintains and relies upon large in-memory tables in order to track allocation of inodes and data blocks. As the size of the file system grows, so will the size of the in-memory tables, which can cause main memory allocation problems.